Ergodicity of Random Walks on Random DFA

摘要

Given a DFA we consider the random walk that starts at the initial state andat each time step moves to a new state by taking a random transition from thecurrent state. This paper shows that for typical DFA this random walk inducesan ergodic Markov chain. The notion of typical DFA is formalized by showingthat ergodicity holds with high probability when a DFA is sampled uniformly atrandom from the set of all automata with a fixed number of states. We also showthe same result applies to DFA obtained by minimizing typical DFA.